|
In combinatorial game theory, the mex, or "''m''inimum ''ex''cludant", of a set of ordinals denotes the smallest ordinal not contained in the set. Some examples: : : : : : where ω is the limit ordinal for the natural numbers. In the Sprague-Grundy theory the minimum excluded ordinal is used to determine the nimber of a normal-play impartial game, which is a game in which either player has the same moves in each position and the last player to move wins. The nimber is equal to 0 for a game that is lost immediately by the first player, and is equal to the mex of the nimbers of all possible next positions for any other game. For example, in a one-pile version of Nim, the game starts with a pile of ''n'' stones, and the player to move may take any positive number of stones. If ''n'' is zero, the nimber is 0. If ''n'' is 1, the player to move will leave 0 stones, and the mex of , 1, gives the nimber for this case. If ''n'' is 2, the player to move can leave 0 or 1 stones, giving 2 as the mex of . In general, the player to move with a pile of ''n'' stones can leave anywhere from 0 to n-1 stones; the mex of the numbers is always ''n''. From this we can conclude that the first player wins if ''n'' is not zero (by taking all the stones). If we change the game so that the player to move can only take up to 3 stones, then when ''n''=4, the successor states have nimbers , giving a mex of 0. Now the first player loses; the second player's strategy is to respond to whatever move the first player makes by taking the rest of the stones. For ''n''=5, the nimbers of the successor states 2, 3, and 4 are 2, 3, and 0 (as we just calculated); the mex of is 1, so starting with 5 stones in this game is a win for the first player. (See nimbers for more details on the meaning of nimber values.) ==References== * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Mex (mathematics)」の詳細全文を読む スポンサード リンク
|